package com.li.algorithm.leetcode.hot100;

public class Test29 {
    /**
     * 解法1:遍历两次，计算长度
     *   时间复杂度：O(L)
     *   空间复杂度：O(1)
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //遍历所有节点，记录链表长度
        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }
        if (len == 0) {
            return null;
        }
        if (n == len) {
            head = head.next;
            return head;
        }
        //再遍历一次，删除第len-n个
        p = head;
        for (int i = 1; i <= len - n - 1; i++) {
            p = p.next;
        }
        p.next = p.next == null ? null : p.next.next;
        return head;
    }

    /**
     * 解法2:双指针
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        int len = 1;
        int num = n;
        ListNode first = head;
        ListNode second = head;
        //first先出发，n个之后second出发，first到达终点时，second就是倒数第n个，此时移除second
        while (first.next != null) {
            len++;
            first = first.next;
            if (n <= 0) {
                second = second.next;
            }
            n--;
        }
        if (len == 1 || len == num) {
            return head.next;
        }
        //移除second
        second.next = second.next.next;
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode p = head;
        for (int i = 2; i <= 2; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
        ListNode result = new Test29().removeNthFromEnd(head, 2);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

}
